# -*- coding:utf-8 -*-
import sys
class Solution:
    def FindGreatestSumOfSubArray(self, array):

        # if len(a) <= 0:
        #     return 0
        #
        # f = [0] * (len(a) + 1)
        # f[1] = a[0]
        # for i in range(1, len(a)+1):
        #     if f[i - 1] + a[i - 1] <= a[i - 1]:
        #         f[i] = a[i - 1]
        #     else:
        #         f[i] = f[i - 1] + a[i - 1]
        # print(f)
        # return max(f)
        # write code here
        if len(a) <= 0:
            return 0

        f = [0] * (len(a) + 1)
        for i in range(1, len(a) + 1):
            if f[i - 1] + a[i - 1] <= a[i - 1]:
                f[i] = a[i - 1]
            else:
                f[i] = f[i - 1] + a[i - 1]
        return max(f[1:])


        # masx = -sys.maxsize
        # a  = array[0]
        # for i in range(1,len(array)):
        #     if array[i] >= a +array[i]:
        #         a =array[i]
        #     else:
        #         a = a + array[i]
        #     if a>masx:
        #         masx = a
        # return masx




a= [2,8,1,5,9]
s =Solution()
m =s.FindGreatestSumOfSubArray(a)
print(m)